/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-14
 * Time: 18:04
 */
public class Sort {
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //每遍历一遍，有i个元素已经冒泡到尾部了
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

    //冒泡排序_优化
    public static void bubbleSortOptimize(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //添加标记
            boolean mark = true;
            //每遍历一遍，有i个元素已经冒泡到尾部了
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    //发生交换标记发生改变
                    mark = false;
                }
            }

            //如果一轮遍历标记无变化，说明序列已经有序
            if (mark) {
                return;
            }
        }
    }

    //交换数组中的两个数
    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //快速排序
    public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    //快速排序的核心操作
    private static void quick(int[] arr,int i,int j) {
        if (i >= j) {
            return;
        }
        int k = find(arr,i,j);

        //处理左子序列
        quick(arr,i,k-1);

        //处理右子序列
        quick(arr,k+1,j);
    }
    //找基准值的下标
    private static int find(int[] arr,int i,int j) {
        //基准值下标
        int k = i;
        //基准值
        int pivot = arr[k];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,k,i);
        return i;
    }
}
